class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       int n = nums.size();
        vector<int> ind(n);
        for (int i = 0; i < n; i++)
        ind[i] = i;
        sort(ind.begin(), ind.end(),
         [&](int i, int j) -> bool { return nums[i] < nums[j];});
        int p1 = 0, p2 = n - 1;
        while (nums[ind[p1]] + nums[ind[p2]] != target) {
        if (nums[ind[p1]] + nums[ind[p2]] < target)
            p1 += 1;
        else
            p2 -= 1;
        }
        vector<int> ret(2);
        ret[0] = ind[p1], ret[1] = ind[p2];
        if (ret[0] > ret[1])
        swap(ret[0], ret[1]);
        return ret; 
    }
};

class Solution2 {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> d;
    vector<int> ret;
    for (size_t i = 0; i < nums.size(); ++i) {
      if (d.find(nums[i]) == d.end()) {
        d[target - nums[i]] = i;
      } else {
        ret.push_back(d[nums[i]]);
        ret.push_back(i);
        break;
      }
    }
    return ret;
  }
};